{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "67925cfb",
   "metadata": {},
   "source": [
    "[101. 对称二叉树 - 力扣（LeetCode）](https://leetcode.cn/problems/symmetric-tree/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "505fbc55",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 递归\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n",
    "        def symmetric(p:TreeNode,q:TreeNode)->bool:\n",
    "            if (not p) and (not q):\n",
    "                return True\n",
    "            if (not p) and q:\n",
    "                return False\n",
    "            if p and (not q):\n",
    "                return False\n",
    "            if p.val!=q.val:\n",
    "                return False\n",
    "            else:\n",
    "                return symmetric(p.left,q.right) and symmetric(p.right,q.left)\n",
    "        \n",
    "        if not root:\n",
    "            return True\n",
    "        return symmetric(root.left,root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef166db6",
   "metadata": {},
   "source": [
    "[102. 二叉树的层序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-level-order-traversal/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "332e2a61",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 使用栈的操作把前一层的节点放置在栈顶，根据栈顶的节点遍历下一层的节点\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        levels = [[root]]\n",
    "        while True:\n",
    "            preLevel = levels[-1]\n",
    "            tmpLst = []\n",
    "            for node in preLevel:\n",
    "                if node.left:\n",
    "                    tmpLst.append(node.left)\n",
    "                if node.right:\n",
    "                    tmpLst.append(node.right)\n",
    "            if tmpLst:\n",
    "                levels.append(tmpLst)\n",
    "            else:\n",
    "                break\n",
    "        res = []\n",
    "        for level in levels:\n",
    "            tmp = []\n",
    "            for node in level:\n",
    "                tmp.append(node.val)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1cd4be0e",
   "metadata": {},
   "source": [
    "[103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b635a92a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        ## 二叉树遍历\n",
    "        if not root:\n",
    "            return []\n",
    "        levels = [[root]]\n",
    "        while True:\n",
    "            preLevel = levels[-1]\n",
    "            recuLevel = []\n",
    "            for node in preLevel:\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "            if recuLevel:\n",
    "                levels.append(recuLevel)\n",
    "            else:\n",
    "                break\n",
    "        flag = True\n",
    "        res = []\n",
    "        for level in levels:\n",
    "            # left->right\n",
    "            tmp = []\n",
    "            if not flag: # 反序的时候翻转层节点的顺序\n",
    "                level = level[::-1]\n",
    "            for node in level:\n",
    "                tmp.append(node.val)\n",
    "            flag = not flag\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2af037d",
   "metadata": {},
   "source": [
    "[104. 二叉树的最大深度 - 力扣（LeetCode）](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b1e8b938",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        levels = [[root]]\n",
    "        while True:\n",
    "            preLevel = levels[-1]\n",
    "            recuLevel = []\n",
    "            for node in preLevel:\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "            if recuLevel:\n",
    "                levels.append(recuLevel)\n",
    "            else:\n",
    "                break\n",
    "        return len(levels)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81b6464e",
   "metadata": {},
   "source": [
    "[105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9bbecff8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "        ## 回复二叉树\n",
    "        # 前序遍历：{root,[left children Tree],[right children Tree]}\n",
    "        # 中序遍历：{[left children Tree],root,[right children Tree]}\n",
    "        dictMap = {val:i for i,val in enumerate(inorder)}\n",
    "        n = len(inorder)\n",
    "        \n",
    "        def recurison(preO_left:int, preO_right:int, inO_left:int, inO_right:int)->Optional[TreeNode]:\n",
    "            ## 边界条件：\n",
    "            if preO_left>preO_right or inO_left>inO_right:\n",
    "                return None\n",
    "            nonlocal preorder, inorder, dictMap\n",
    "            root_val = preorder[preO_left]\n",
    "            root = TreeNode(root_val)\n",
    "            rootIndx_inO = dictMap[root_val]\n",
    "            left_LCT_inO,right_LCT_inO = inO_left,rootIndx_inO-1\n",
    "            left_RCT_inO,right_RCT_inO = rootIndx_inO+1,inO_right\n",
    "            len_LCT = right_LCT_inO-left_LCT_inO+1\n",
    "            left_LCT_preO, right_LCT_preO = preO_left+1, preO_left+len_LCT\n",
    "            left_RCT_preO, right_RCT_preO = right_LCT_preO+1,preO_right\n",
    "\n",
    "            root.left = recurison(left_LCT_preO,right_LCT_preO,left_LCT_inO,right_LCT_inO)\n",
    "            root.right = recurison(left_RCT_preO,right_RCT_preO,left_RCT_inO,right_RCT_inO)\n",
    "\n",
    "            return root\n",
    "\n",
    "        root = recurison(0,n-1,0,n-1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb23f421",
   "metadata": {},
   "source": [
    "[106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）](https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1db08f49",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "## 从中序遍历和后序遍历中恢复二叉树\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        ## 中序遍历 {[Left Children Tree],Root, [Right Children Tree]}\n",
    "        ## 后续遍历 {[Left Children Tree],[Right Children Tree],Root}\n",
    "        dictMap = {val:i for i,val in enumerate(inorder)}\n",
    "        n = len(inorder)\n",
    "\n",
    "        def recursion(left_inO:int,right_inO:int,left_postO:int,right_postO:int)->Optional[TreeNode]:\n",
    "            if left_inO>right_inO or left_postO>right_inO:\n",
    "                return None\n",
    "            \n",
    "            nonlocal inorder,postorder,dictMap\n",
    "            val = postorder[right_postO]\n",
    "            rootIndx_inO = dictMap[val]\n",
    "            root = TreeNode(val)\n",
    "            left_LCT_inO,right_LCT_inO = left_inO,rootIndx_inO-1\n",
    "            left_RCT_inO,right_RCT_inO = rootIndx_inO+1,right_inO\n",
    "\n",
    "            len_LCT = right_LCT_inO-left_LCT_inO+1\n",
    "\n",
    "            left_LCT_postO,right_LCT_postO = left_postO,left_postO+len_LCT-1\n",
    "            left_RCT_postO,right_RCT_postO = right_LCT_postO+1,right_postO-1\n",
    "\n",
    "            root.left = recursion(left_LCT_inO,right_LCT_inO,left_LCT_postO,right_LCT_postO)\n",
    "            root.right = recursion(left_RCT_inO,right_RCT_inO,left_RCT_postO,right_RCT_postO)\n",
    "\n",
    "            return root\n",
    "\n",
    "        return recursion(0,n-1,0,n-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "930b1070",
   "metadata": {},
   "source": [
    "[107. 二叉树的层序遍历 II - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a87101ea",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "            \n",
    "        levels = [[root]]\n",
    "        while True:\n",
    "            preLevel = levels[-1]\n",
    "            recuLevel = []\n",
    "            for node in preLevel:\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "            if recuLevel:\n",
    "                levels.append(recuLevel)\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        res = []\n",
    "        levels = levels[::-1]\n",
    "        for level in levels:\n",
    "            tmp = []\n",
    "            for node in level:\n",
    "                tmp.append(node.val)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46936cff",
   "metadata": {},
   "source": [
    "[108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f8065261",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        def func(left:int,right:int)->Optional[TreeNode]:\n",
    "            if left>right:\n",
    "                return None\n",
    "            nonlocal nums\n",
    "            mid = left+((right-left)>>1)\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = func(left,mid-1)\n",
    "            root.right = func(mid+1,right)\n",
    "            return root\n",
    "        return func(0,len(nums)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17a884ef",
   "metadata": {},
   "source": [
    "[109. 有序链表转换二叉搜索树 - 力扣（LeetCode）](https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9746ad8a",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 先把链表转为列表，然后和上题一致\n",
    "\n",
    "# coding=utf-8\n",
    "from optparse import Option\n",
    "from typing import List,Optional\n",
    "\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:\n",
    "        lst = []\n",
    "        reader = head\n",
    "        while reader:\n",
    "            lst.append(reader.val)\n",
    "            reader = reader.next\n",
    "        \n",
    "        def func(left:int,right:int)->Optional[TreeNode]:\n",
    "            if left>right:\n",
    "                return None\n",
    "\n",
    "            nonlocal lst\n",
    "            mid = left + ((right-left)>>1)\n",
    "            root = TreeNode(lst[mid])\n",
    "            root.left = func(left,mid-1)\n",
    "            root.right = func(mid+1,right)\n",
    "            return root\n",
    "        \n",
    "        return func(0,len(lst)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fda499e2",
   "metadata": {},
   "source": [
    "[110. 平衡二叉树 - 力扣（LeetCode）](https://leetcode.cn/problems/balanced-binary-tree/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "de08a4fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from optparse import Option\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n",
    "        ## 递归判定，\n",
    "        # 从底层向上查找每个节点的左右子树高度\n",
    "        # 如果其左右子树的高度差大于1即为不高度平衡\n",
    "        \n",
    "        def height(root:Optional[TreeNode])->int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            leftH = height(root.left)\n",
    "            rightH = height(root.right)\n",
    "\n",
    "            if leftH==-1 or rightH==-1 or abs(rightH-leftH)>=2:\n",
    "                return -1\n",
    "            return max(leftH,rightH)+1\n",
    "\n",
    "        return height(root)!=-1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf8f14d8",
   "metadata": {},
   "source": [
    "[111. 二叉树的最小深度 - 力扣（LeetCode）](https://leetcode.cn/problems/minimum-depth-of-binary-tree/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9aed00bb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        ## 自上至下遍历树的每一层，直到某一层含有不存在左右子树的节点，该层的深度就是\n",
    "        if not root:\n",
    "            return 0\n",
    "        levels = [[root]]\n",
    "        while True:\n",
    "            preLevel = levels[-1]\n",
    "            recuLevel = []\n",
    "            flag = True\n",
    "            for node in preLevel:\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "            for node in recuLevel:\n",
    "                if (not node.left) and (not node.right):\n",
    "                    flag = False\n",
    "            if recuLevel:\n",
    "                levels.append(recuLevel)\n",
    "                if not flag:\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return len(levels)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a6c99b7",
   "metadata": {},
   "source": [
    "[112. 路径总和 - 力扣（LeetCode）](https://leetcode.cn/problems/path-sum/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0f4b17fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        \n",
    "        reSums = []\n",
    "        flag = True\n",
    "        def calcSum(root: Optional[TreeNode],accumu:int)->None:\n",
    "            nonlocal flag\n",
    "            if (not root.left) and (not root.right):\n",
    "                accumu += root.val\n",
    "                if accumu==targetSum:\n",
    "                    flag = False\n",
    "                    return\n",
    "                else:\n",
    "                    return\n",
    "            if not flag:\n",
    "                return\n",
    "                \n",
    "            accumu += root.val\n",
    "            if root.left:\n",
    "                calcSum(root.left,accumu)\n",
    "            if root.right:\n",
    "                calcSum(root.right,accumu)\n",
    "        \n",
    "        calcSum(root,0)\n",
    "        return True if not flag else False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f75e10d",
   "metadata": {},
   "source": [
    "[113. 路径总和 II - 力扣（LeetCode）](https://leetcode.cn/problems/path-sum-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a6189896",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 自顶向下遍历每个节点，直到遇到叶子节点\n",
    "#  判断叶子节点的条件，(not root.left) and (not root.right)\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        from copy import deepcopy\n",
    "        ## 递归找到所有和的路径，然后筛选\n",
    "        if not root:\n",
    "            return []\n",
    "        allPaths = []\n",
    "        def allpathSum(root:Optional[TreeNode],path:List[int])->None:\n",
    "            nonlocal allPaths\n",
    "            if (not root.left) and (not root.right):\n",
    "                path.append(root.val)\n",
    "                allPaths.append(path)\n",
    "                return\n",
    "            \n",
    "            path.append(root.val)\n",
    "            if root.left:\n",
    "                allpathSum(root.left,deepcopy(path))\n",
    "            if root.right:\n",
    "                allpathSum(root.right,deepcopy(path))\n",
    "        \n",
    "        allpathSum(root,[])\n",
    "        res = []\n",
    "        for path in allPaths:\n",
    "            if sum(path)==targetSum:\n",
    "                res.append(path)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67473f3d",
   "metadata": {},
   "source": [
    "[114. 二叉树展开为链表 - 力扣（LeetCode）](https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "314b046d",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 先进行先序遍历，然后构建数组\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        nodes = []\n",
    "        def preOrder(root:Optional[TreeNode])->None:\n",
    "            if root:\n",
    "                nodes.append(root)\n",
    "                preOrder(root.left)\n",
    "                preOrder(root.right)\n",
    "        \n",
    "        preOrder(root)\n",
    "\n",
    "        head = nodes[0]\n",
    "        head.left=None\n",
    "        reader = head\n",
    "        for i in range(1,len(nodes)):\n",
    "            reader.right = nodes[i]\n",
    "            reader = reader.right\n",
    "            reader.left = None\n",
    "        reader.right = None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c100223e",
   "metadata": {},
   "source": [
    "[115. 不同的子序列 - 力扣（LeetCode）](https://leetcode.cn/problems/distinct-subsequences/)\n",
    "\n",
    "**动态规划**\n",
    "\n",
    "- 一个模型：多阶段决策最优解模型\n",
    "- 三个性质：最优子问题，无后效性，重复子问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "85ad3120",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def numDistinct(self, s: str, t: str) -> int:\n",
    "\n",
    "        ## 递归 超时\n",
    "        ## 使用动态规划\n",
    "        # define： dp[i][j] 表示s[i:] 中含有t[j:]的字符串个数\n",
    "        # if s[i]==t[j]:\n",
    "        #   1) 使用s[i]匹配t[i], dp[i+1][j+1]\n",
    "        #   2) 不使用s[i]匹配t[i], dp[i+1][j]\n",
    "        # else:\n",
    "        #   dp[i+1][j]\n",
    "        if len(s)<len(t):\n",
    "            return 0\n",
    "        n,m = len(s),len(t)\n",
    "        \n",
    "        dp = [[0]*(m+1) for _ in range(n+1)]\n",
    "        # initial\n",
    "        for i in range(n+1):\n",
    "            dp[i][m] = 1\n",
    "        for i in range(m):\n",
    "            dp[n][i] = 0\n",
    "        \n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(m-1,-1,-1):\n",
    "                if s[i]==t[j]:\n",
    "                    dp[i][j] = dp[i+1][j+1]+dp[i+1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i+1][j]\n",
    "        \n",
    "        return dp[0][0]\n",
    " \n",
    "if __name__=='__main__':\n",
    "    s = \"rabbbit\"\n",
    "    t = \"rabbit\"\n",
    "    solv = Solution()\n",
    "    print(solv.numDistinct(s,t))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26609562",
   "metadata": {},
   "source": [
    "[116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）](https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f08bc6e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        ## 使用先序遍历的方法\n",
    "        def connectRB(root:Optional[Node],RightB:Optional[Node])->None:\n",
    "            if root:\n",
    "                root.next = RightB\n",
    "                connectRB(root.left,root.right)\n",
    "                if root.next and root.next.left:\n",
    "                    connectRB(root.right,root.next.left)\n",
    "                else:\n",
    "                    connectRB(root.right,None)\n",
    "                            \n",
    "        connectRB(root,None)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "582a1506",
   "metadata": {},
   "source": [
    "[117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）](https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eacd3d6b",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 解法一，使用列表进行BFS\n",
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        ## BFS思想，罗列每一层的节点，把当前节点的next指向同层的下一个节点\n",
    "        levels = [[root]]\n",
    "\n",
    "        while True:\n",
    "            preLevel = levels[-1]\n",
    "            recuLevel = []\n",
    "            for node in preLevel:\n",
    "                if node.left:\n",
    "                    recuLevel.append(node.left)\n",
    "                if node.right:\n",
    "                    recuLevel.append(node.right)\n",
    "            if recuLevel:\n",
    "                levels.append(recuLevel)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        for level in levels:\n",
    "            for i in range(len(level)-1):\n",
    "                level[i].next = level[i+1]\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4674e4a7",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 解法二： 使用链表的方法遍历上一层节点，和当前层节点\n",
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        # 使用链表遍历每一层\n",
    "        # 两个链表头，一个链表头遍历上一层的节点，另一个把当前层的节点连在一起\n",
    "        # 利用第一个链表串联第二个链表，然后第二个链表变成第一个链表，串联下一层的节点\n",
    "\n",
    "        root.next = None\n",
    "        preRd = root  # 第一个链表\n",
    "        head0 = Node(0)  # 第二个链表\n",
    "        while True:\n",
    "            curRd = head0 # 使用第二链表串联当前层的节点\n",
    "            while preRd:\n",
    "                if preRd.left:\n",
    "                    curRd.next = preRd.left\n",
    "                    curRd = curRd.next\n",
    "                if preRd.right:\n",
    "                    curRd.next = preRd.right\n",
    "                    curRd = curRd.next\n",
    "                preRd = preRd.next\n",
    "            curRd.next = None\n",
    "\n",
    "            if not head0.next: # 第二个链表中没有节点，表示当前层没有节点了，结束\n",
    "                break\n",
    "            else: # 第二个链表中有节点，将其变为第一个链表，\n",
    "                preRd = head0.next\n",
    "                \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2bd9278c",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 解法三： 使用队列+BFS\n",
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        import queue\n",
    "\n",
    "        # 使用queue+BFS 遍历每一层\n",
    "        q = queue.Queue()\n",
    "        q.put(root)\n",
    "        head0 = Node(0)\n",
    "        while not q.empty():\n",
    "            pre = head0\n",
    "            levelLen = q.qsize()  # 当前层的节点数目\n",
    "            for i in range(levelLen): # 遍历当前层的所有节点\n",
    "                nd = q.get()\n",
    "                pre.next = nd\n",
    "                pre = pre.next\n",
    "                if nd.left:    # 扩展队列\n",
    "                    q.put(nd.left)\n",
    "                if nd.right:\n",
    "                    q.put(nd.right)\n",
    "\n",
    "            pre.next = None\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6163043",
   "metadata": {},
   "source": [
    "[118. 杨辉三角 - 力扣（LeetCode）](https://leetcode.cn/problems/pascals-triangle/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d3c4d6ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "## 直接模拟\n",
    "\n",
    "class Solution:\n",
    "    def generate(self, numRows: int) -> List[List[int]]:\n",
    "        if numRows==1:\n",
    "            return [[1]]\n",
    "        levels = [[1],[1,1]]\n",
    "        for i in range(2,numRows):\n",
    "            preLevel = levels[-1]\n",
    "            recuLevel = [0]*(i+1)\n",
    "            recuLevel[0],recuLevel[-1]=1,1\n",
    "            for j in range(1,i):\n",
    "                recuLevel[j] = preLevel[j-1]+preLevel[j]\n",
    "            \n",
    "            levels.append(recuLevel)\n",
    "            \n",
    "        return levels"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66de2b12",
   "metadata": {},
   "source": [
    "[119. 杨辉三角 II - 力扣（LeetCode）](https://leetcode.cn/problems/pascals-triangle-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63258a4c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getRow(self, rowIndex: int) -> List[int]:\n",
    "        if rowIndex == 0:\n",
    "            return [1]\n",
    "        if rowIndex == 1:\n",
    "            return [1, 1]\n",
    "\n",
    "        preLevel = [1, 1]\n",
    "        for i in range(2, rowIndex+1):\n",
    "            recuLevel = [0]*(i+1)\n",
    "            recuLevel[0], recuLevel[-1] = 1, 1\n",
    "            for j in range(1, i):\n",
    "                recuLevel[j] = preLevel[j-1]+preLevel[j]\n",
    "\n",
    "            preLevel = recuLevel\n",
    "\n",
    "        return recuLevel\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e7a872e",
   "metadata": {},
   "source": [
    "[120. 三角形最小路径和 - 力扣（LeetCode）](https://leetcode.cn/problems/triangle/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "60beb04f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotal(self, triangle: List[List[int]]) -> int:\n",
    "        # 回溯的方法超时\n",
    "        # 使用动态规划的思想\n",
    "        # dp[L][i] = min(dp[L-1][i]+TA[L][i], dp[L-1][i-1]+TA[L][i])\n",
    "\n",
    "        if len(triangle) == 1:\n",
    "            return triangle[0][0]\n",
    "        preLevels = [triangle[0][0]]  # 存储到达当前层相应位置的最小值\n",
    "        for i in range(1, len(triangle)):\n",
    "            recuLevel = triangle[i]\n",
    "            for j in range(len(recuLevel)):\n",
    "                if j == 0:\n",
    "                    recuLevel[j] += preLevels[j]\n",
    "                    continue\n",
    "                if j == len(recuLevel)-1:\n",
    "                    recuLevel[j] += preLevels[j-1]\n",
    "                    continue\n",
    "\n",
    "                recuLevel[j] += min(preLevels[j-1], preLevels[j])\n",
    "            preLevels = recuLevel\n",
    "\n",
    "        return min(recuLevel)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]\n",
    "    solv = Solution()\n",
    "    print(solv.minimumTotal(triangle))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
